package com.atguigu.srb.base.algorithm;

import org.springframework.util.StopWatch;

/**
 * @ClassName Solution8
 * @Describe
 * @Author Wangchengshan
 * @Date 2023/6/13 16:29
 * @Version 1.0
 **/
public class Solution8 {
    //复写零
    //给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
    //
    //注意：请不要在超过该数组长度的位置写入元素。空间复杂度小于O(n)
    //
    //输入：arr = [1,0,2,3,0,4,5,0]
    //输出：[1,0,0,2,3,0,0,4]
    //
    //输入：arr = [1,2,3]
    //输出：[1,2,3]
    //
//    public static int[] duplicateZeros2(int[] arr) {
//        //空间复杂度O(n)
//        int lh = 0;
//        int arrlh = 0;
//        int maxlh = arr.length - 1;
//        int[] reArr = new int[arr.length];
//        while (lh < maxlh) {
//            if (arr[arrlh] == 0) {
//                reArr[lh] = arr[arrlh];
//                lh++;
//                reArr[lh] = arr[arrlh];
//                lh++;
//                arrlh++;
//            } else {
//                reArr[lh] = arr[arrlh];
//                lh++;
//                arrlh++;
//            }
//            if (lh == maxlh) {
//                reArr[maxlh] = arr[arrlh];
//            }
//        }
//        return reArr;
//    }

    public static int[] duplicateZeros(int[] arr) {
        int st = 0;
        int end = arr.length;

        while (st < end) {
            if (arr[st] == 0) {
                end--;
            }
            st++;
        }

        int lh = arr.length - 1;
        if (end < st) {
            arr[lh--] = arr[end--];
        } else {
            end--;
        }
        while (end >= 0) {
            if (arr[end] != 0) {
                arr[lh--] = arr[end];
            } else {
                arr[lh--] = 0;
                arr[lh--] = 0;
            }
            end--;
        }
        return arr;
    }

    public static void main(String[] args) {
        StopWatch sw = new StopWatch("time");
        int[] arr = new int[]{1, 0, 2, 3, 0, 4, 5, 0};
        int[] arr2 = new int[]{1, 0, 2, 3, 0, 0, 5, 0};//10023000
        int[] arr1 = new int[]{1, 2, 3};
        int[] arr3 = new int[]{1, 0, 2};
        int[] arr4 = new int[]{0, 1, 2};
        sw.start();
        int[] result = duplicateZeros(arr2);
        sw.stop();
        for (int i : result) {
            System.out.println("result : " + i);
        }

        System.out.println(sw.prettyPrint());
    }
}
